{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data manipulation with numpy: tips and tricks, part 2\n",
    "\n",
    "More examples on fast manipulations with data using numpy.\n",
    "\n",
    "First part may be found [here](/2015/09/29/NumpyTipsAndTricks1.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rolling window,  strided tricks \n",
    "\n",
    "When working with time series / images it is frequently needed to do some operations on windows.\n",
    "\n",
    "Simplest case: taking mean for running window:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sequence = np.random.normal(size=10000) + np.arange(10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Very bad idea__ is to do this with pure python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([   49.27774499,    50.25852659,    51.26151649, ...,  9947.32841776,\n",
       "        9948.3391695 ,  9949.33539463])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def running_average_simple(seq, window=100):\n",
    "    result = np.zeros(len(seq) - window + 1)\n",
    "    for i in range(len(result)):\n",
    "        result[i] = np.mean(seq[i:i + window])\n",
    "    return result\n",
    "\n",
    "running_average_simple(sequence)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A bit better is to use `as_strided`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from numpy.lib.stride_tricks import as_strided\n",
    "def running_average_strides(seq, window=100):\n",
    "    stride = seq.strides[0]\n",
    "    sequence_strides = as_strided(seq, shape=[len(seq) - window + 1, window], strides=[stride, stride])\n",
    "    return sequence_strides.mean(axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([   49.27774499,    50.25852659,    51.26151649, ...,  9947.32841776,\n",
       "        9948.3391695 ,  9949.33539463])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "running_average_strides(sequence)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From computation side, __as_strided__ does nothing. No copies and no computations, it only gives new view to the data, which is two-dimensional this time. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## numpy.cumsum\n",
    "\n",
    "However the right way to compute mean over rolling window is using numpy.cumsum:\n",
    "\n",
    "(this one is unbeatable in speed if `n` is not small)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def running_average_cumsum(seq, window=100):\n",
    "    s = np.insert(np.cumsum(seq), 0, [0])\n",
    "    return (s[window :] - s[:-window]) * (1. / window)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([   49.27774499,    50.25852659,    51.26151649, ...,  9947.32841776,\n",
       "        9948.3391695 ,  9949.33539463])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "running_average_cumsum(sequence)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "See also for this purpose: \n",
    "* scipy.signal.smooth\n",
    "* pandas.rolling_mean and [similar functions](http://pandas.pydata.org/pandas-docs/stable/computation.html#moving-rolling-statistics-moments)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remark__: `numpy.cumsum` is equivalent to `numpy.add.accumulate`,\n",
    "but there are also:\n",
    "* `numpy.maximum.accumulate`, `numpy.minimum.accumulate` - running max and min\n",
    "* `numpy.multiply.accumulate`, which is equivalent to `numpy.cumprod`\n",
    "\n",
    "__Remark__: for computing rolling mean, `numpy.cumsum` is best, however for other window statistics like min/max/percentile, use strides trick. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Strides and training on sequences\n",
    "\n",
    "ML algorithms in python are often taking `numpy.arrays`. In many cases when working with sequences you need to pass some data many times as part of different chunks. \n",
    "\n",
    "Example: you have exhange rates for a year, you want GBDT to predict next exchange rate based on the previous 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "window = 10\n",
    "rates = np.random.normal(size=1000)\n",
    "# target in training\n",
    "y = rates[window:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Typically the solution used is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "X1 = np.zeros([len(rates) - window, window])\n",
    "for day in range(len(X1)):\n",
    "    X1[day, :] = rates[day:day + window]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But strided tricks are better way, since they don't need additional space:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "stride, = rates.strides\n",
    "X2 = as_strided(rates, [len(rates) - window , window], strides=[stride, stride])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.allclose(X1, X2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And if I want to pass not each window, but with some gap (to speed up training usually), I use slicing, which again does no operations with data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "X_new = X2[::3]\n",
    "y_new = y[::3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Strides and images\n",
    "\n",
    "The same tricks work with images. For instance, for each window of size `[window_w, window_h]` we want to compute max, mean and variance. Let's compare naive and strided approach."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_window_mean_and_var(image, window_w, window_h):\n",
    "    w, h = image.shape\n",
    "    w_new, h_new = w - window_w + 1, h - window_h + 1\n",
    "    means = np.zeros([w_new, h_new])\n",
    "    maximums = np.zeros([w_new, h_new])\n",
    "    variations = np.zeros([w_new, h_new])\n",
    "    for i in range(w_new):\n",
    "        for j in range(h_new):\n",
    "            window = image[i:i+window_w, j:j+window_h]\n",
    "            means[i, j] = np.mean(window)\n",
    "            maximums[i, j] = np.max(window) \n",
    "            variations[i, j] = np.var(window) \n",
    "    return means, maximums, variations    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_window_mean_and_var_strided(image, window_w, window_h):\n",
    "    w, h = image.shape\n",
    "    strided_image = np.lib.stride_tricks.as_strided(image, \n",
    "                                                    shape=[w - window_w + 1, h - window_h + 1, window_w, window_h],\n",
    "                                                    strides=image.strides + image.strides)\n",
    "    # important: trying to reshape image will create complete 4-dimensional compy\n",
    "    means = strided_image.mean(axis=(2,3)) \n",
    "    mean_squares = (strided_image ** 2).mean(axis=(2, 3)) \n",
    "    maximums = strided_image.max(axis=(2,3))\n",
    "    \n",
    "    variations = mean_squares - means ** 2\n",
    "    return means, maximums, variations    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "image = np.random.random([500, 500])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 11.1 s, sys: 230 ms, total: 11.4 s\n",
      "Wall time: 12.8 s\n"
     ]
    }
   ],
   "source": [
    "%time a1, b1, c1 = compute_window_mean_and_var(image, 20, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 626 ms, sys: 282 ms, total: 908 ms\n",
      "Wall time: 928 ms\n"
     ]
    }
   ],
   "source": [
    "%time a2, b2, c2 = compute_window_mean_and_var_strided(image, 20, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, True, True)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.allclose(a1, a2), np.allclose(b1, b2), np.allclose(c1, c2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remark__: `numpy.cumsum` allows awesomely fast computations in this case as well (but not for the max). Find out how!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Oblivious decision trees\n",
    "\n",
    "Oblivious decision tree is tree, which has the same splits in all nodes at particular depth.\n",
    "\n",
    "ODT of depth $n$ consists of $n$ pairs (feature index, split) and $2^n$ real values, which correspond to predictions in each leaf."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def predict_odt(data, features, splits, leaf_values):\n",
    "    # first compute leaf for each sample in data\n",
    "    leaf_indices = np.zeros(len(data), dtype=int)\n",
    "    for feature, split in zip(features, splits):\n",
    "        leaf_indices *= 2\n",
    "        leaf_indices += data[:, feature] > split\n",
    "        \n",
    "    predictions = leaf_values[leaf_indices]\n",
    "    return predictions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's it. It was really simple, now let's create some fake data and fake ODT to measure speed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "data = np.random.normal(size=[100000, 11])\n",
    "\n",
    "depth = 7\n",
    "features = np.arange(depth)\n",
    "splits = np.random.normal(size=depth).astype('float32')\n",
    "leaf_values = np.random.random(2 ** depth).astype('float32')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 6.45 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit predict_odt(data, features, splits, leaf_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is good result, but can we do this faster? Let's apply bitwise operations instead of arithmetical."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def predict_odt_bit_operations(data, features, splits, leaf_values):\n",
    "    leaf_indices = np.zeros(len(data), dtype='uint8')\n",
    "    for feature, split in zip(features, splits):\n",
    "        leaf_indices <<= 1\n",
    "        leaf_indices |= data[:, feature] > split\n",
    "        \n",
    "    predictions = leaf_values[leaf_indices]\n",
    "    return predictions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 5.43 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit predict_odt_bit_operations(data, features, splits, leaf_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, but what if we apply __bitwise operations for 64-bit integers__? This should require __8 times less operations__, because currently there are 8-bit operations (not handled natively by 64bit procesors).\n",
    "\n",
    "Result of computation is the same, but this requires the length of data to be divisible by 8.\n",
    "\n",
    "This trick significantly speeds up shift `<<` and bitwise or `|` in the code, and the major part of time (>80%) is now spent on checking conditions.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def predict_odt_fast(data, features, splits, leaf_values):\n",
    "    leaf_indices = np.zeros(len(data), dtype='uint8').view('uint64')\n",
    "    for feature, split in zip(features, splits):\n",
    "        leaf_indices <<= 1\n",
    "        leaf_indices |= (data[:, feature] > split).view('uint64')\n",
    "    \n",
    "    predictions = leaf_values[leaf_indices.view('uint8')]\n",
    "    return predictions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 4.42 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit predict_odt_fast(data, features, splits, leaf_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Banks in RAM, strides and order of elements\n",
    "\n",
    "Data in `numpy` is stored as continuous chunk of data. This gives high flexibility (instant transpositions, reshaping, views and strided tricks), but sometimes we need to keep eye on strides (in particular, orders of dimensions).\n",
    "\n",
    "In the following simple example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 6.89 ms per loop\n",
      "1000 loops, best of 3: 754 µs per loop\n"
     ]
    }
   ],
   "source": [
    "data = np.random.random([100000, 64]).astype(order='C', dtype='float32')\n",
    "%timeit predict_odt_fast(data, features, splits, leaf_values)\n",
    "\n",
    "data = np.random.random([100000, 64]).astype(order='F', dtype='float32')\n",
    "%timeit predict_odt_fast(data, features, splits, leaf_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### How happened we have this huge difference in speed? \n",
    "\n",
    "Operations with sequential data is faster due to CPU cache.\n",
    "By default, `numpy` uses C-order, thus elements from one column are far each from other, \n",
    "while elements within row are placed in memory together.\n",
    "\n",
    "C-order is fine when operating rows, while our ODT code uses column-wise operations.\n",
    "\n",
    "The actual speed up may significantly differ on the structure of your CPU cache, but anyway is expected to be high.\n",
    "\n",
    "Specially this is pressing when stride is some power of 2 due to banks of memory, which are used to get parallel access to memory. In C-order the distance between two closest elements in a column:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "256"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.random.random([10000, 64]).astype(order='C', dtype='float32').strides[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "stride is 256. We will use each time single memory bank, which is worst situation possible.\n",
    "\n",
    "__Conclusion__: order of indexing matters. Mind the cache."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Computing optimal step for AdaLoss function\n",
    "\n",
    "In GBDT there is important step after training a tree is finding optimal values in leaves.\n",
    "\n",
    "AdaLoss (also known as ExpLoss) can be written as (here $y_i = \\pm 1$):\n",
    "\n",
    "$$ \\sum_i \\exp[-y_i d(x_i)]$$\n",
    "\n",
    "Contrary to other losses, for AdaLoss one can write exact expression of optimal value of a leaf:\n",
    "\n",
    "$$ \\text{leaf\_value} = \\frac{1}{2} \\log \\left( \\dfrac{w_{leaf,+}}{w_{leaf, -}} \\right),  $$\n",
    "\n",
    "where $w_{leaf,+}, w_{leaf, -}$ are weights of signal and background events in the leaf. Let's write this procedure in beautiful `numpy` code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def compute_optimal_leaf_values(terminal_regions, labels, predictions):\n",
    "    \"\"\"\n",
    "    terminal regions are integers, correspong to the number of leaf each event belongs to\n",
    "    labels are +1 and -1\n",
    "    predictions are real numbers - sum of predictions given by previous trees in boosting\n",
    "    \"\"\"\n",
    "    weights = np.exp(- labels * predictions)\n",
    "    w_plus = np.bincount(terminal_regions, weights * (labels == +1))\n",
    "    w_minus = np.bincount(terminal_regions, weights * (labels == -1))\n",
    "    return np.log(w_leafs / w_minus) / 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Logistic function\n",
    "\n",
    "Logistic function is frequently used in machine learning to convert real-valued output to probability:\n",
    "$$ \\sigma (x) = \\dfrac{e^x}{e^x + 1} = \\dfrac{1}{1 + e^{-x}} $$\n",
    "\n",
    "However, it is a bad idea to use this definition directly, because:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def logistic(x):\n",
    "    return np.exp(x) / (1 + np.exp(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/axelr/.venvs/rep/lib/python2.7/site-packages/ipykernel/__main__.py:2: RuntimeWarning: overflow encountered in exp\n",
      "  from ipykernel import kernelapp as app\n",
      "/Users/axelr/.venvs/rep/lib/python2.7/site-packages/ipykernel/__main__.py:2: RuntimeWarning: invalid value encountered in double_scalars\n",
      "  from ipykernel import kernelapp as app\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "nan"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "logistic(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First expression fails. Second expression raises warning, but returns correct answer (but earlier numpy returned Nan in this case as well).\n",
    "\n",
    "Instead use `scipy.special.expit`, which is fast and reliable:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from scipy.special import expit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0. ,  0.5,  1. ])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "expit([-1000, 0, 1000])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Logistic loss function\n",
    "\n",
    "being expressed via decision function, logistic loss for single event has the following expression:\n",
    "\n",
    "$$ LogLoss = \\log(1 + e^{-yd}) $$\n",
    "\n",
    "For simplicity, let's implement the function\n",
    "$$\\log(1 + e^x)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def logloss(x):\n",
    "    return np.log(1 + np.exp(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/axelr/.venvs/rep/lib/python2.7/site-packages/ipykernel/__main__.py:2: RuntimeWarning: overflow encountered in exp\n",
      "  from ipykernel import kernelapp as app\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([   1.31326169,   10.0000454 ,  100.        ,           inf])"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "logloss([1, 10, 100, 1000])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Whoops, something went wrong.__ Of course, there was an overflow after applying exponent. Resulting number didn't fit in float64.\n",
    "\n",
    "Use `numpy.logaddexp` to avoid these problems!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([    1.31326169,    10.0000454 ,   100.        ,  1000.        ])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.logaddexp(0, [1, 10, 100, 1000])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remark__: `numpy.logaddexp.at` is a good replacement for `numpy.maximum.at` if you want to keep 'soft' maximum.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Masked array\n",
    "\n",
    "`numpy` doesn't support jagged arrays. But this can be partially resolved by using masked arrays.\n",
    "\n",
    "Imagine the following situation: there are $n$ houses, we want to select location to build new house. \n",
    "For each position we analyze the price of $k$ neighbouring houses to guess the best place.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "houses_prices = np.random.exponential(size=10000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "n_neighs = 20\n",
    "position_neighbours = np.random.randint(0, len(houses_prices), size=[100000, n_neighs])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "computing __average price__ of nearest houses is fairly simple:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.85558849,  0.85929689,  1.18028179, ...,  1.02167602,\n",
       "        0.96623028,  1.04202728])"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "houses_prices[position_neighbours].mean(axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "same method is used to get total/min/max/std price of closest houses.\n",
    "\n",
    "The problem is compute these things when part of the data shall be ignored. For instance, \n",
    "houses which are very expensive (top 5%) are probably expensive not due to their position. Can we ignore them when computing average?\n",
    "\n",
    "__Masked arrays__ come to the rescue:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "masked_array(data = [0.6948163814376606 0.8592968871648994 1.0309823904276911 ...,\n",
       " 0.8899183280916126 0.8485975161178317 1.0420272772084531],\n",
       "             mask = [False False False ..., False False False],\n",
       "       fill_value = 1e+20)"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# ignore houses with higher price\n",
    "max_price = np.percentile(houses_prices, 95)\n",
    "\n",
    "data = houses_prices[position_neighbours]\n",
    "ignored = houses_prices[position_neighbours] > max_price\n",
    "\n",
    "# pay attention that data[~ignored] will return one-dimensional array,\n",
    "# that's why we need masked arrays\n",
    "masked_prices = np.ma.MaskedArray(data=data, mask=ignored)\n",
    "\n",
    "masked_prices.mean(axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.69481638,  0.85929689,  1.03098239, ...,  0.88991833,\n",
       "        0.84859752,  1.04202728])"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.array(masked_prices.mean(axis=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Numpy.ufunc.reduceat to work with multicategories.\n",
    "\n",
    "Multicategory is type of feature: each sample in dataset can belong to several (possibly zero) groups. \n",
    "\n",
    "For instance, samples are people, and we have informations about which languages they are programing. Programming languages are multicategory.\n",
    "\n",
    "Assume we have two parallel arrays, corresponding pair denote programmer id and language id he/she knows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[   0    0    0 ..., 1999 1999 1999]\n",
      "[15  8  3 ..., 11 11 28]\n"
     ]
    }
   ],
   "source": [
    "salaries = np.random.random(2000)\n",
    "programers = np.sort(np.random.randint(0, len(salaries), size=10000))\n",
    "languages = np.random.randint(0, 50, size=len(programers))\n",
    "\n",
    "print(programers)\n",
    "print(languages)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's compute for each language average salary of its users:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lang_average_salaries = np.bincount(languages, salaries[programers]) / np.bincount(languages)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For fun, now we can compute the salary programmer can obtain for best-payed of his languages:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.50898484  0.48684316  0.51820748 ...,  0.54239297  0.54239297\n",
      "  0.51820748]\n"
     ]
    }
   ],
   "source": [
    "programmer_top_salary = np.zeros(programers.max() + 1)\n",
    "np.maximum.at(programmer_top_salary, programers, lang_average_salaries[languages])\n",
    "\n",
    "print(programmer_top_salary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Get the id of best-payed language\n",
    "\n",
    "We can guess the language based on price, but this can be inreliable in other cases. \n",
    "\n",
    "Let's combine tricks studied earlier:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "lang_sorter = np.argsort(lang_average_salaries)\n",
    "# languages ranked by average salaries:\n",
    "lang_salaries_ordered = np.argsort(lang_sorter)\n",
    "\n",
    "programmer_top_language = np.zeros(programers.max() + 1, dtype=int)\n",
    "np.maximum.at(programmer_top_language, programers, lang_salaries_ordered[languages])\n",
    "\n",
    "# now we need to decode order of language back to original ID\n",
    "programmer_top_language = lang_sorter[programmer_top_language]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 3,  2,  7, ..., 27, 27,  7])"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "programmer_top_language"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Checking with previous result &mdash; taking average salaries for top languages.\n",
    "\n",
    "NB: there were programmers with no languages - their 'top language' became the worst payed one.\n",
    "Maybe worth creating special pseudo-language to denote this situations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.50898484,  0.48684316,  0.51820748, ...,  0.54239297,\n",
       "        0.54239297,  0.51820748])"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lang_average_salaries[programmer_top_language]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## numpy.ufunc.reduceat\n",
    "\n",
    "Numpy.maximum.at is not fast at this moment, though very convenient. \n",
    "\n",
    "Let's show faster, but more complicated way using:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sorter = np.argsort(programers)\n",
    "ordered_programers = programers[sorter]\n",
    "ordered_languages = languages[sorter]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "limits_in_programmers = np.insert(np.bincount(programers).cumsum()[:-1], 0, [0])\n",
    "programmer_top_salary = np.maximum.reduceat(lang_average_salaries[ordered_languages], limits_in_programmers) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remark__:\n",
    "* `numpy.ufunc.reduceat` has inobvious behavior when the list of categories is empty. In this case the value for first category of next sample is returned.\n",
    "* significant degradation in speed happens when too few categories for samples. When one category per sample, speed is comparable to `numpy.ufunc.at`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sparse arrays and multicategories\n",
    "\n",
    "There is an alternative to `numpy.bincount`, specially handy when using 'weights'. \n",
    "\n",
    "Minor modification of previous example: each programmer has the `skill` value, describing how well he knows programming language (and plays a role of weight). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "skills = np.random.random(len(languages)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sparse matrices contain all this information together:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from scipy.sparse import coo_matrix\n",
    "matrix = coo_matrix((skills, (programers, languages)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Easy tricks with normalizations are strong side of sparse matrices. \n",
    "\n",
    "Let's compute average salary with weights proportional to 'skill'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "matrix_normed_for_language = matrix / (matrix.sum(axis=0) + 0.01)\n",
    "lang_average_salaries = matrix_normed_for_language.T.dot(salaries)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 1.98991879],\n",
       "        [ 0.30377964],\n",
       "        [ 1.22430908],\n",
       "        ..., \n",
       "        [ 1.42907617],\n",
       "        [ 1.78078234],\n",
       "        [ 1.80980639]])"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "matrix.dot(lang_average_salaries.T)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sparse matrices are slower if used only once (compared to `bincount`), because of matrix creation,\n",
    "but faster when applied many times.\n",
    "\n",
    "## Fast computing of efficiencies for group\n",
    "\n",
    "In `uBoost` algorithm we need to compute many times local efficiencies:\n",
    "for each event which part of its neighbors pass the given threshold. Sparse matrix is a good option in this case. Close things happen in other classifiers (`uGB+kNN`, `RankBoost`)\n",
    "\n",
    "As an exercise, let's compute which part of programmers knowing language `X` have salary greater then `salary_threshold` (printing result only for first 5 languages):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.99989806  0.99991087  0.99990149  0.99988927  0.99988925]]\n",
      "[[ 0.84027866  0.85943743  0.87756901  0.86609172  0.899259  ]]\n",
      "[[ 0.71429575  0.77817814  0.74757531  0.75081062  0.77426352]]\n",
      "[[ 0.61629482  0.6186105   0.61793111  0.63928084  0.65908296]]\n",
      "[[ 0.52584106  0.50824714  0.50906984  0.55588072  0.53273126]]\n",
      "[[ 0.41138264  0.35382012  0.44019973  0.44312564  0.43501221]]\n",
      "[[ 0.29691138  0.24084839  0.31622935  0.37518756  0.33608273]]\n",
      "[[ 0.21323651  0.18827297  0.2335139   0.28325233  0.22044709]]\n",
      "[[ 0.1371795   0.06998397  0.1376106   0.14013846  0.09387452]]\n",
      "[[ 0.  0.  0.  0.  0.]]\n"
     ]
    }
   ],
   "source": [
    "for salary_threshold in np.linspace(0, 1, 10):\n",
    "    print(matrix_normed_for_language.T.dot(salaries > salary_threshold)[0, :5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fast residual\n",
    "\n",
    "when having deal with words or other categorical variables, there are frequently troubles with applying one-hot encoding (don't want to keep the mapping or too many parameters for model).\n",
    "\n",
    "Hashing trick is good alternative: each value is mapped by hash to small number.\n",
    "\n",
    "Funny fact is that integer resudial is not very cheap operation, though shall be applied many times:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "categories = np.random.randint(0, 1e10, size=1000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 13.7 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit categories % 128"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "if you select the number of left features to be power of 2, you can do the same with bitmask:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 3.01 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit categories & 127"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "how about rocket speed? (please don't apply in practice, just to show this is not the limit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 loops, best of 3: 1.02 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "mask = np.array(127, dtype='int64')\n",
    "for _ in range(8):\n",
    "    mask |= mask << 8\n",
    "result = (categories.view('uint8')[::8].copy().view('uint64') & mask).view('uint8')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "please keep such simple bit-tricks in mind if you're going to implement some algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Online statistics\n",
    "\n",
    "Finally, let's implement online statistics computation. In this case we can use only information about past.\n",
    "\n",
    "For instance, for each category we can compute how many times it was used in the past. This is called online counter.\n",
    "\n",
    "### Online counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# plain python approach\n",
    "from collections import defaultdict\n",
    "\n",
    "def compute_online_counter(categories_stream):\n",
    "    online_counter = np.zeros_like(categories_stream)\n",
    "    counters = defaultdict(int)\n",
    "    for i in range(len(categories_stream)):\n",
    "        online_counter[i] = counters[categories_stream[i]]\n",
    "        counters[categories_stream[i]] += 1\n",
    "    return online_counter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simple example for online counter\n",
    "each time we compute how many times each number (representing a category) presented before in the stream"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 0, 1, 2, 0, 1, 0, 0, 1, 2, 3])"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_online_counter([1, 2, 1, 1, 3, 2, 5, 6, 3, 3, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "categories_stream = np.random.randint(0, 10000, size=1000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 609 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit online_counter = compute_online_counter(categories_stream)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_online_counter_numpy(categories_stream):\n",
    "    occurences = np.bincount(categories_stream)\n",
    "    before = occurences.cumsum() - occurences\n",
    "    positions = categories_stream.argsort(kind='mergesort').argsort(kind='mergesort')\n",
    "    return positions - before[categories_stream]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 264 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit compute_online_counter_numpy(categories_stream)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "this is the situation when numpy is really not of much help. Sorting applied twice is bad approach when no sorting shall be used.\n",
    "\n",
    "`pandas` suggests a good one-line alternative, but it is ..hmhm.. _a bit slow_."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 956 ms, sys: 5.42 ms, total: 962 ms\n",
      "Wall time: 965 ms\n"
     ]
    }
   ],
   "source": [
    "import pandas\n",
    "df = pandas.DataFrame({'cat':  categories_stream, 'ones': np.ones(len(categories_stream))})\n",
    "# truncating to first 10000, otherwise it will never finish\n",
    "df = df[:10000]\n",
    "%time result = df.groupby('cat')['ones'].transform(pandas.Series.cumsum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, then it is time to use some external tool. Let's do it with parakeet."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import parakeet\n",
    "parakeet.config.backend = 'c' # one thread\n",
    "\n",
    "@parakeet.jit\n",
    "def compute_online_counter_parakeet(categories_stream):\n",
    "    counters = np.zeros(np.max(categories_stream) + 1)\n",
    "    online_counter = np.zeros_like(categories_stream)\n",
    "    for i in range(len(categories_stream)):\n",
    "        online_counter[i] = counters[categories_stream[i]]\n",
    "        counters[categories_stream[i]] += 1\n",
    "    return online_counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 9.7 ms per loop\n"
     ]
    }
   ],
   "source": [
    "compute_online_counter_parakeet(categories_stream)\n",
    "%timeit compute_online_counter_parakeet(categories_stream)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, keep in mind, that you'll probably not be able to use this code in windows OS. Use external tools only when they are really needed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion\n",
    "\n",
    "* numpy is very powerful if properly used. \n",
    "* learning numpy is harder than a + b, but it gives benefit in shortness and readability\n",
    "* there are very few cases when you really need to switch from python code to cython or c during research.\n",
    "* many of things from above can be implemented in other vector environments: theano / matlab / R \n",
    "\n",
    "\n",
    "# Links \n",
    " \n",
    "\n",
    "There are many more things to know about numpy. Here are the some helpful links you may also be interested in:\n",
    "\n",
    "1. [Getting the Best Performance out of NumPy](http://ipython-books.github.io/featured-01/)\n",
    "2. [Game of life and numpy reference](http://www.labri.fr/perso/nrougier/teaching/numpy/numpy.html)\n",
    "3. [100 numpy exercises](http://www.labri.fr/perso/nrougier/teaching/numpy.100/index.html)\n",
    "4. [Advanced numpy](https://scipy-lectures.github.io/advanced/advanced_numpy/)\n",
    "5. [Tentative numpy tutorial](http://wiki.scipy.org/Tentative_NumPy_Tutorial)\n",
    "6. [IPython cookbook](https://github.com/ipython-books/cookbook-code)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
